package utils;

import java.util.ArrayList;

/**
 * Created by Pavel Nikolaev
 */

public final class KmpMatcher {
    private ArrayList<Integer> myPrefixFunction;
    private ArrayList<Integer> myResults;
    private static int ourReservedSize = 10;

    public KmpMatcher() {
        myPrefixFunction = new ArrayList<Integer>(ourReservedSize);
        myResults = new ArrayList<Integer>();
    }

    public ArrayList<Integer> getResults() {
        return myResults;
    }

    private void preprocessPattern(String pattern) {
        myPrefixFunction.clear();
        myPrefixFunction.add(0);
        int k = 0;
        for (int q = 1; q < pattern.length(); ++q) {
            while ((k > 0) && (pattern.charAt(k) != pattern.charAt(q))) {
                k = myPrefixFunction.get(k - 1);
            }
            if (pattern.charAt(k) == pattern.charAt(q)) ++k;
            myPrefixFunction.add(k);
        }
    }

    private void reset() {
        myResults.clear();
    }

    public boolean match(char[] text, int len, String pattern) {
        reset();
        preprocessPattern(pattern);

        int m = pattern.length();
        int q = 0;
        for (int i = 0; i < len; ++i) {
            while ((q > 0) && (pattern.charAt(q) != text[i])) {
                q = myPrefixFunction.get(q - 1);
            }
            if (pattern.charAt(q) == text[i]) ++q;
            if (q == m) {
                myResults.add(i - m + 1);
                q = myPrefixFunction.get(q - 1);
            }
        }

        return !myResults.isEmpty();
    }
}
